//The n-queens puzzle is the problem of placing n queens on an n x n chessboard 
//such that no two queens attack each other. 
//
// Given an integer n, return all distinct solutions to the n-queens puzzle. 
//
// Each solution contains a distinct board configuration of the n-queens' placem
//ent, where 'Q' and '.' both indicate a queen and an empty space, respectively. 
//
// 
// Example 1: 
//
// 
//Input: n = 4
//Output: [[".Q..",
//          "...Q",
//         "Q...",
//         "..Q."],
// ["..Q.","Q...","...Q",".Q.."]]
//Explanation: There exist two distinct solutions to the 4-queens puzzle as show
//n above
// 
//
// Example 2: 
//
// 
//Input: n = 1
//Output: [["Q"]]
// 
//
// 
// Constraints: 
//
// 
// 1 <= n <= 9 
// 
// Related Topics 回溯算法 
// 👍 879 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：N-Queens
class P51NQueens {
    public static void main(String[] args) {
        Solution solution = new P51NQueens().new Solution();
        // TO TEST
        System.out.println(solution.solveNQueens(4));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<String>> res = new ArrayList<>();

        public List<List<String>> solveNQueens(int n) {
            char[][] matrix = new char[n][n];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    matrix[i][j] = '.';
                }
            }
            solveNQueens(matrix, 0, new ArrayList<>());
            return res;
        }

        private void solveNQueens(char[][] matrix, int row, List<char[]> list) {
            if (row == matrix.length) {
                List<String> stringList = new ArrayList<>();
                for (char[] chars : list) {
                    stringList.add(new String(chars));
                }
                res.add(stringList);
                return;
            }
            for (int col = 0; col < matrix[0].length; col++) {
                if (isValid(row, col, matrix)) {
                    matrix[row][col] = 'Q';
                    list.add(0, matrix[row]);
                    solveNQueens(matrix, row + 1, list);
                    matrix[row][col] = '.';
                    list.remove(0);
                }
            }
        }

        /* 是否可以在 board[row][col] 放置皇后 */
        boolean isValid(int row, int col, char[][] board) {
            int n = board.length;
            // 检查列是否有皇后互相冲突
            for (int i = 0; i < n; i++) {
                if (board[i][col] == 'Q') {
                    return false;
                }
            }
            // 检查右上⽅是否有皇后互相冲突
            for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
                if (board[i][j] == 'Q') {
                    return false;
                }
            }
            // 检查左上⽅是否有皇后互相冲突
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                if (board[i][j] == 'Q') {
                    return false;
                }
            }
            return true;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}